package com.gzq.leet;

import com.gzq.leet.commen.struct.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class No94LDR {

    //中序遍历：左，根，右
    //递归版
    public List<Integer> inorderTraversal_recursion(TreeNode root){
        List<Integer> list = new ArrayList<>();
        if(root == null) return list;
        boolean noLeft=(root.left==null);
        boolean noRight=(root.right==null);

        if(!noLeft){//尽量避免创建空的list对象
            list.addAll(inorderTraversal_recursion(root.left));
        }
        list.add(root.val);
        if(!noRight){
            list.addAll(inorderTraversal_recursion(root.right));
        }
        return list;
    }
    //中序遍历，迭代版
    //基本思路：仿照递归的过程，调用栈化身节点栈，即把节点树拍平到栈中，按我们希望的次序遍历。
    public List<Integer> inorderTraversal_iteration(TreeNode root){
        List<Integer> list = new ArrayList<>();
        if(root == null) return list;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode tar=root;
        while(tar!=null || !stack.isEmpty()){ //循环条件的tar!=null，避免了在最顶层，根节点右子树遍历时跳出。因为在刚进入右子树时，栈会清空
            if(tar!=null){//注意！ if(tar.left!=null)是绝对不对的，会陷入不停计算左节点的循环
                stack.push(tar);//备份自己
                tar=tar.left; //进入左子树
            }else{
                TreeNode last=stack.pop();//左子树到头了，返回最近的父节点
                list.add(last.val);//中序计算
                tar=last.right;//无条件进入右子树
            }
        }
        return list;
    }
    //中序遍历，迭代版2.比上个版本思路更清晰
    public List<Integer> inorderTraversal_iteration_v2(TreeNode root){
        List<Integer> list = new ArrayList<>();
        if(root == null) return list;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode tar = root;

        do{
            if(tar!=null){
                stack.push(tar);
                tar = tar.left;
            }else{
                tar = stack.pop();
                list.add(tar.val);
                tar=tar.right;
            }
        }while(tar!=null||!stack.isEmpty());
        return list;
    }

    //前序遍历：根，左子树，右子树
    public List<Integer> preorderTraversal_iteration(TreeNode node){
        if (node == null) {
            return null;
        }
        List<Integer> list = new ArrayList<Integer>();
        Stack<TreeNode> s = new Stack<TreeNode>();
        s.push(node);
        while(!s.isEmpty()){
            TreeNode tar = s.pop();
            list.add(tar.val);
            if(tar.right!=null){
                s.push(tar.right);
            }
            if(tar.left!=null){
                s.push(tar.left);
            }
        }

        return list;
    }
    //后序遍历 版本1
    public List<Integer> postorderTraversal_iteration_no_good(TreeNode node){
        if (node == null) {
            return null;
        }
        List<Integer> list = new ArrayList<Integer>();
        Stack<TreeNode> s = new Stack<TreeNode>();
        s.push(node);

        while( !s.isEmpty() ) {
            TreeNode tar = s.pop();
            if(tar.left != null) {
                s.push(tar.left);
            }
            if(tar.right != null) {
                s.push(tar.right);
            }
            list.add(0, tar.val);//不太好
        }

        return list;
    }

    public List<Integer> postorderTraversal_iteration(TreeNode node){
        if (node == null) {
            return null;
        }
        List<Integer> list = new ArrayList<Integer>();
        Stack<TreeNode> s = new Stack<TreeNode>();
        s.push(node);

        while( !s.isEmpty() ) {
            TreeNode tar = s.pop();
            if(tar.left != null) {
                s.push(tar.left);
            }
            if(tar.right != null) {
                s.push(tar.right);
            }
            list.add(0, tar.val);//TODO 不太好
        }

        return list;
    }
}

